package com.hdit.ds
{
	import flash.utils.setInterval;

	/**
	 * 二叉堆
	 **/
	public class BinaryHeap
	{
		
		private var _heap:Vector.<Object>;
		private var _compare:Function;
		
		/**
		 * 构造函数
		 * @param  compare 比较方法,@return int 
		 **/
		public function BinaryHeap(compare:Function = null)
		{
			_heap=new Vector.<Object>();
			_compare=compare;
			if(compare==null)
				_compare =  function compare(a:int,b:int):int{return (b-a);};
		}
		
		/**
		 * 入队,新加元素
		 * @param element 入列数据
		 **/
		public function enqueue(element:Object):void
		{ 
			
			this._heap.push(element);
			trace("\n");
			trace("heap.length:"+this._heap.length);
			//初始父节点索引    提示:堆长度*0.5 取整
			var parentIndex:int = (this._heap.length-1)>> 1;
			trace("parentIndex:"+parentIndex);
			//初始当前插入对象索引
			var objIndex:int = this._heap.length -1;
			trace("objIndex:"+objIndex);
			//缓存被插入对象
			var temp:* = this._heap[objIndex];
				
			while(objIndex>0) 
			{
				if(_compare(temp,this._heap[parentIndex])>0) 
				{
					this._heap[objIndex] = this._heap[parentIndex]; 
					objIndex = parentIndex;
					parentIndex = (parentIndex-1)>>1;
				}
				else
					break;
			} 
			_heap[objIndex] = temp;
		}
		
		/**
		 * 列表入列
		 **/
		public function enqueueByList(list:Array):void
		{
			for (var i:int = 0; i < list.length; i++) 
			{
				enqueue(list[i]);
			}
		}
		 
		
		/**
		 * 获取堆顶元素
		 **/
		public function getTopOfHeap():Object
		{
			return _heap[0];
		}
		
		/**
		 * 返回堆中所有元素
		 **/
		public function getHeap():Vector.<Object>
		{
			return _heap;
		}
		
		/**
		 * 清空堆
		 **/
		public function clearHeap():void
		{
			_heap.length=0;
		}
	}
}